{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sparse Similarity LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: computeSimilarities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #稀疏相似度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。它们的相似度非常&ldquo;稀疏&rdquo;，也就是说任选 2 个文档，相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。</p>\n",
    "\n",
    "<p>输入为一个二维数组 <code>docs</code>，<code>docs[i]</code>&nbsp;表示&nbsp;id 为 <code>i</code> 的文档。返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，其格式为 <code>{id1},{id2}: {similarity}</code>，其中 <code>id1</code> 为两个文档中较小的 id，<code>similarity</code> 为相似度，精确到小数点后 4 位。以任意顺序返回数组均可。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> \n",
    "<code>[\n",
    "&nbsp; [14, 15, 100, 9, 3],\n",
    "&nbsp; [32, 1, 9, 3, 5],\n",
    "&nbsp; [15, 29, 2, 6, 8, 7],\n",
    "&nbsp; [7, 10]\n",
    "]</code>\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "&nbsp; &quot;0,1: 0.2500&quot;,\n",
    "&nbsp; &quot;0,2: 0.1000&quot;,\n",
    "&nbsp; &quot;2,3: 0.1429&quot;\n",
    "]</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>docs.length &lt;= 500</code></li>\n",
    "\t<li><code>docs[i].length &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sparse-similarity-lcci](https://leetcode.cn/problems/sparse-similarity-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sparse-similarity-lcci](https://leetcode.cn/problems/sparse-similarity-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for i in range(n - 1):\n",
    "            doc1 = set(docs[i])\n",
    "            for j in range(i + 1, n):\n",
    "                doc2 = set(docs[j])\n",
    "                same = doc1.intersection(doc2)\n",
    "                # 如果没有交集\n",
    "                if not same:\n",
    "                    continue\n",
    "                len1 = len(same)\n",
    "                len2 = len(doc1) + len(doc2) - len1\n",
    "                res = len1 / len2 + minn\n",
    "                ans.append('{},{}: {:.4f}'.format(i, j, res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        ans=[]\n",
    "        n=len(docs)\n",
    "        for i in range(n):\n",
    "            a = set(docs[i])\n",
    "            for j in range(i+1,n):\n",
    "                b = docs[j]\n",
    "                arr = a.intersection(b)\n",
    "                if not arr:\n",
    "                    continue\n",
    "                m = len(a)+len(b)-len(arr) #并集长度\n",
    "                res = len(arr)/m+1e-9\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i,j,res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        def similarity(a,b):\n",
    "            dic={}\n",
    "            for i in a:\n",
    "                if i in dic:\n",
    "                    dic[i]+=1\n",
    "                else:\n",
    "                    dic[i]=1\n",
    "            com=0\n",
    "            #diff=0\n",
    "            for i in b:\n",
    "                if i in dic.keys() and dic[i]>0:\n",
    "                    com+=1\n",
    "            diff_a=len(a)-com\n",
    "\n",
    "            return com/(diff_a+len(b))+1e-9\n",
    "\n",
    "        res=[]\n",
    "        for i in range(len(docs)-1):\n",
    "            for j in range(i+1,len(docs)):\n",
    "                s=similarity(docs[i],docs[j])\n",
    "                #print(i,',',j,':',s)\n",
    "                if s>1e-9:\n",
    "                    res.append(str(i)+','+str(j)+': '+str(\"%.4f\" %s))\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def computeSimilarities1(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs):\n",
    "        list_data = []\n",
    "        for i in range(0, len(docs)):\n",
    "            for j in range(i+1, len(docs)):\n",
    "                num = (len(docs[i] + docs[j]) - len(set(docs[i] + docs[j]))) / len(set(docs[i] + docs[j]))\n",
    "                if num > 0:\n",
    "                    multiplier = 10000\n",
    "                    rounded_num = int(num * multiplier + 0.5) / multiplier\n",
    "                    formatted_num = \"{:.4f}\".format(rounded_num)\n",
    "                    list_data.append(str(i) + \",\" + str(j) + \": \" + formatted_num)\n",
    "        return list(set(list_data))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                a,b = set(docs[i]), set(docs[j])\n",
    "                r,c = len(a)+len(b),len(a.union(b))\n",
    "                if r!=c:\n",
    "                    similarity = 1.0*r/c-1+1e-9\n",
    "                    ans.append(\"%d,%d: %.4f\"%(i,j,similarity))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        ans=[]\n",
    "        n=len(docs)\n",
    "        for i in range(n):\n",
    "            a = set(docs[i])\n",
    "            for j in range(i+1,n):\n",
    "                b = docs[j]\n",
    "                # arr = a.intersection(b)\n",
    "                arr=len(a.intersection(b))\n",
    "                if not arr:\n",
    "                    continue\n",
    "                m = len(a)+len(b)-arr #并集长度\n",
    "                res = arr/m+1e-9\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i,j,res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            l1 = len(docs[i])\n",
    "            doc = set(docs[i])\n",
    "            for j in range(i+1, n):\n",
    "                l2 = len(docs[j])\n",
    "                intersection = 0\n",
    "                union = l1 + l2\n",
    "                for v in docs[j]:\n",
    "                    if v in doc:\n",
    "                        union -= 1\n",
    "                        intersection += 1\n",
    "                if intersection > 0:\n",
    "                    res.append(f'{i},{j}: {format(intersection/union + 1e-9, \".4f\")}')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        def similarity(a,b):\n",
    "            dic={}\n",
    "            for i in a:\n",
    "                if i in dic:\n",
    "                    dic[i]+=1\n",
    "                else:\n",
    "                    dic[i]=1\n",
    "            com=0\n",
    "            #diff=0\n",
    "            for i in b:\n",
    "                if i in dic.keys() and dic[i]>0:\n",
    "                    com+=1\n",
    "                    dic[i]-=1\n",
    "            diff_a=len(a)-com\n",
    "\n",
    "            return com/(diff_a+len(b))+1e-9\n",
    "\n",
    "        res=[]\n",
    "        for i in range(len(docs)-1):\n",
    "            for j in range(i+1,len(docs)):\n",
    "                s=similarity(docs[i],docs[j])\n",
    "                #print(i,',',j,':',s)\n",
    "                if s>1e-9:\n",
    "                    res.append(str(i)+','+str(j)+': '+str(\"%.4f\" %s))\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def computeSimilarities1(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def main(docs):\n",
    "    res = []\n",
    "    for i in range(len(docs) - 1):\n",
    "        doc1 = set(docs[i])\n",
    "        for j in range(i + 1, len(docs)):\n",
    "            doc2 = set(docs[j])\n",
    "            its = doc1.intersection(doc2)\n",
    "            if not its:\n",
    "                continue\n",
    "            res.append('{},{}: {:.4f}'.format(i, j, len(its) / (len(doc1) + len(doc2) - len(its))+1e-9))\n",
    "    return res\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        return main(docs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def computeSimilarities(self, docs):\n",
    "        \"\"\"\n",
    "        :type docs: List[List[int]]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                union = set(docs[i] + docs[j])\n",
    "                intersection = len(docs[i]) + len(docs[j]) - len(union)\n",
    "                similarity = round(intersection / len(union) + 1e-9, 4)\n",
    "                if similarity > 0:\n",
    "                    result.append(f\"{i},{j}: {similarity:.4f}\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                l = len(set(docs[i] + docs[j]))\n",
    "                m = len(docs[i]) + len(docs[j])\n",
    "                if m > l:\n",
    "                    r = float((m - l) / l)\n",
    "                    res.append(\"%d,%d: %.4f\" % (i, j, round(r+0.00001, 4) if r * 100000 % 10 == 5 else round(r, 4)))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lenintersection(set1, lst):\n",
    "    n = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            n += 1\n",
    "    return n\n",
    "\n",
    "\n",
    "def func1(docs):\n",
    "    n = len(docs)\n",
    "    res = []\n",
    "    for i in range(n - 1):\n",
    "        a = set(docs[i])\n",
    "        for j in range(i + 1, n):\n",
    "            b = docs[j]\n",
    "            n_a, n_b = len(a), len(b)\n",
    "            n_c = get_lenintersection(a, b)\n",
    "            if n_c == 0:\n",
    "                continue\n",
    "            minn = 1e-9\n",
    "            r = n_c / (n_a + n_b - n_c) + minn\n",
    "            res.append('{},{}: {:.4f}'.format(i, j, r))\n",
    "    return res\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        return func1(docs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for i in range(n - 1):\n",
    "            doc1 = set(docs[i])\n",
    "            for j in range(i + 1, n):\n",
    "                doc2 = docs[j]\n",
    "                len1 = lenintersection(doc1, doc2)\n",
    "                #doc2 = set(docs[j])\n",
    "                #same = doc1.intersection(doc2)\n",
    "                # 如果没有交集\n",
    "                #if not same:\n",
    "                #   continue\n",
    "                # len1 = len(same)\n",
    "                if len1 == 0:\n",
    "                    continue\n",
    "                len2 = len(doc1) + len(doc2) - len1\n",
    "                res = len1 / len2 + minn\n",
    "                ans.append('{},{}: {:.4f}'.format(i, j, res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs):\n",
    "        res = []\n",
    "        n = len(docs)\n",
    "        for i in range(n - 1):\n",
    "            if not docs[i]:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if not docs[j]:\n",
    "                    continue\n",
    "                li = len(set(docs[i]).intersection(docs[j]))\n",
    "                if li == 0:\n",
    "                    continue\n",
    "                l1 = len(docs[i])\n",
    "                l2 = len(docs[j])\n",
    "                tl = l1 + l2 - li\n",
    "                res.append(\"{},{}: {:.4f}\".format(i, j, (li / tl)+1e-9))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def func1(lst1,lst2):\n",
    "#     sum_int = 0\n",
    "#     for i in lst1:\n",
    "#         if i in lst2:\n",
    "#             sum_int += 1\n",
    "#     return sum_int\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                n1 = len(docs[i])\n",
    "                n2 = len(docs[j])\n",
    "                n3 = len(set(docs[i]).intersection(docs[j]))\n",
    "                # n3 = func1(docs[i],docs[j])\n",
    "                if n3 == 0:\n",
    "                    continue\n",
    "                n4 = n1+n2-n3\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i,j,n3/n4+1e-9))\n",
    "        return ans\n",
    "        # res = {}\n",
    "        # n = len(docs)\n",
    "        # for i in range(n):\n",
    "        #     for j in docs[i]:\n",
    "        #         if j not in res:\n",
    "        #             res[j] = []\n",
    "        #         res[j].append(i)\n",
    "        # res1 = {}\n",
    "        # for id1,id2 in res.items():\n",
    "        #     if len(id2) == 1:\n",
    "        #         continue\n",
    "        #     for l in range(len(id2)-1):\n",
    "        #         for m in range(l+1,len(id2)):\n",
    "        #             i = id2[l]\n",
    "        #             j = id2[m]\n",
    "        #             if (i,j) not in res1:\n",
    "        #                 res1[(i,j)] = 0\n",
    "        #             res1[(i,j)] += 1\n",
    "        # ans = []\n",
    "        # for id1,id2 in res1.items():\n",
    "        #     i,j = id1\n",
    "        #     n1 = len(docs[i])\n",
    "        #     n2 = len(docs[j])\n",
    "        #     n3 = n1+n2-id2\n",
    "        #     ans.append(\"{},{}: {:.4f}\".format(i,j,id2/n3+1e-9))\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "\n",
    "        n = len(docs)\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i+1,n):\n",
    "                lst1 = docs[i]\n",
    "                lst2 = docs[j]\n",
    "                assert len(lst1) == len(set(lst1))\n",
    "                assert len(lst2) == len(set(lst2))\n",
    "                tmp = set(lst1).intersection(set(lst2))\n",
    "                if not tmp:\n",
    "                    continue\n",
    "                minn = 1e-9\n",
    "                length = len(tmp)/(len(lst1) + len(lst2) - len(tmp)) + minn\n",
    "                res.append(\"{0:d},{1:}: {2:.4f}\".format(i,j,length))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def func1(lst1,lst2):\n",
    "#     sum_int = 0\n",
    "#     for i in lst1:\n",
    "#         if i in lst2:\n",
    "#             sum_int += 1\n",
    "#     return sum_int\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                n1 = len(docs[i])\n",
    "                n2 = len(docs[j])\n",
    "                n3 = len(set(docs[i]).intersection(docs[j]))\n",
    "                if n3 == 0:\n",
    "                    continue\n",
    "                n4 = n1+n2-n3\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i,j,n3/n4+1e-9))\n",
    "        return ans\n",
    "        # res = {}\n",
    "        # n = len(docs)\n",
    "        # for i in range(n):\n",
    "        #     for j in docs[i]:\n",
    "        #         if j not in res:\n",
    "        #             res[j] = []\n",
    "        #         res[j].append(i)\n",
    "        # res1 = {}\n",
    "        # for id1,id2 in res.items():\n",
    "        #     if len(id2) == 1:\n",
    "        #         continue\n",
    "        #     for l in range(len(id2)-1):\n",
    "        #         for m in range(l+1,len(id2)):\n",
    "        #             i = id2[l]\n",
    "        #             j = id2[m]\n",
    "        #             if (i,j) not in res1:\n",
    "        #                 res1[(i,j)] = 0\n",
    "        #             res1[(i,j)] += 1\n",
    "        # ans = []\n",
    "        # for id1,id2 in res1.items():\n",
    "        #     i,j = id1\n",
    "        #     n1 = len(docs[i])\n",
    "        #     n2 = len(docs[j])\n",
    "        #     n3 = n1+n2-id2\n",
    "        #     ans.append(\"{},{}: {:.4f}\".format(i,j,id2/n3+1e-9))\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i+1,n):\n",
    "                lst1 = docs[i]\n",
    "                lst2 = docs[j]\n",
    "                tmp = get_len_intersection(set(lst1),set(lst2))\n",
    "                if not tmp:\n",
    "                    continue\n",
    "                minn = 1e-9\n",
    "                length = tmp/(len(lst1) + len(lst2) - tmp) + minn\n",
    "                res.append(\"{},{}: {:.4f}\".format(i,j,length))\n",
    "        return res\n",
    "def get_len_intersection(set1,set2):\n",
    "    n = 0\n",
    "    for v1 in set1:\n",
    "        if v1 in set2:\n",
    "            n += 1\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersectCount(self, doc1: Set[int], doc2: Set[int]) -> int:\r\n",
    "        count = 0\r\n",
    "        for data in doc1:\r\n",
    "            if data in doc2:\r\n",
    "                count += 1\r\n",
    "        return count\r\n",
    "\r\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\r\n",
    "        docs = [(len(doc), set(doc)) for doc in docs]\r\n",
    "        ans = []\r\n",
    "        for i in range(0, len(docs)):\r\n",
    "            if docs[i][0] == 0:\r\n",
    "                continue\r\n",
    "            for j in range(i + 1, len(docs)):\r\n",
    "                count = self.intersectCount(docs[i][1], docs[j][1])\r\n",
    "                if count == 0:\r\n",
    "                    continue\r\n",
    "                similarity = count / (docs[i][0] + docs[j][0] - count)\r\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i, j, similarity + 1e-9))\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersectCount(self, doc1: Set[int], doc2: Set[int]) -> int:\r\n",
    "        count = 0\r\n",
    "        for data in doc1:\r\n",
    "            if data in doc2:\r\n",
    "                count += 1\r\n",
    "        return count\r\n",
    "\r\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\r\n",
    "        docs = [(len(doc), set(doc)) for doc in docs]\r\n",
    "        ans = []\r\n",
    "        for i in range(0, len(docs)):\r\n",
    "            if docs[i][0] == 0:\r\n",
    "                continue\r\n",
    "            for j in range(i + 1, len(docs)):\r\n",
    "                count = self.intersectCount(docs[i][1], docs[j][1])\r\n",
    "                if count == 0:\r\n",
    "                    continue\r\n",
    "                similarity = (count) / (docs[i][0] + docs[j][0] - count)\r\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i, j, similarity + 1e-9))\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        N = len(docs)\n",
    "        docs = [set(d) for d in docs]\n",
    "        ret = []\n",
    "\n",
    "        for id1, s1 in enumerate(docs):\n",
    "            for id2 in range(id1 + 1, N):\n",
    "                s2 = docs[id2]\n",
    "                \n",
    "                inter = len(s1 & s2)\n",
    "                if inter:\n",
    "                    sim = \"%0.04f\" % (int(inter/len(s1 | s2)*10000 + 0.5)/10000)\n",
    "                    ret.append(f\"{id1},{id2}: {sim}\")\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        docs = [set(i) for i in docs]\n",
    "        return [\"{:d},{:d}: {:.4f}\".format(j, i, 1e-8+len(docs[j] & docs[i])/len(docs[i] | docs[j])) for i, j in combinations(reversed(range(len(docs))), 2) if docs[j] & docs[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersectCount(self, doc1: Set[int], doc2: Set[int]) -> int:\r\n",
    "        count = 0\r\n",
    "        for data in doc1:\r\n",
    "            if data in doc2:\r\n",
    "                count += 1\r\n",
    "        return count\r\n",
    "\r\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\r\n",
    "        docs = [(len(doc), set(doc)) for doc in docs]\r\n",
    "        ans = []\r\n",
    "        for i in range(0, len(docs)):\r\n",
    "            if docs[i][0] == 0:\r\n",
    "                continue\r\n",
    "            for j in range(i + 1, len(docs)):\r\n",
    "                count = self.intersectCount(docs[i][1], docs[j][1])\r\n",
    "                if count == 0:\r\n",
    "                    continue\r\n",
    "                similarity = (count) / (docs[i][0] + docs[j][0] - count)\r\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i, j, similarity+1e-9))\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "            n=len(docs)\n",
    "            total=[]\n",
    "            ret=[]\n",
    "            for i in range(n):\n",
    "                temp=set()\n",
    "                total.append(temp)\n",
    "                dup=[0]*i\n",
    "                for num in docs[i]:\n",
    "                    total[i].add(num)\n",
    "                    for j in range(i):\n",
    "                        if num in total[j]:\n",
    "                            dup[j]+=1\n",
    "                for k in range(i):\n",
    "                    if dup[k]:\n",
    "                        ret.append(str(k)+','+str(i)+': '+str(format(dup[k]/(len(docs[k])+len(docs[i])-dup[k])+1e-9,'.4f')))\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectCount(self, doc1: Set[int], doc2: Set[int]) -> int:\n",
    "        count = 0\n",
    "        for data in doc1:\n",
    "            if data in doc2:\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        docs = [(len(doc), set(doc)) for doc in docs]\n",
    "        ans = []\n",
    "        for i in range(0, len(docs)):\n",
    "            if docs[i][0] == 0:\n",
    "                continue\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                count = self.intersectCount(docs[i][1], docs[j][1])\n",
    "                if count == 0:\n",
    "                    continue\n",
    "                similarity = (count) / (docs[i][0] + docs[j][0] - count)\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i, j, similarity + 1e-9))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersectCount(self, doc1: Set[int], doc2: Set[int]) -> int:\r\n",
    "        count = 0\r\n",
    "        for data in doc1:\r\n",
    "            if data in doc2:\r\n",
    "                count += 1\r\n",
    "        return count\r\n",
    "\r\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\r\n",
    "        docs = [(len(doc), set(doc)) for doc in docs]\r\n",
    "        ans = []\r\n",
    "        for i in range(0, len(docs)):\r\n",
    "            if docs[i][0] == 0:\r\n",
    "                continue\r\n",
    "            for j in range(i + 1, len(docs)):\r\n",
    "                count = self.intersectCount(docs[i][1], docs[j][1])\r\n",
    "                if count == 0:\r\n",
    "                    continue\r\n",
    "                similarity = (count) / (docs[i][0] + docs[j][0] - count)\r\n",
    "                ans.append(\"{},{}: {:.4f}\".format(i, j, similarity + 1e-9))\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        mydict = {}\n",
    "        for i in range(n):\n",
    "            mydict[i] = set(docs[i])\n",
    "        # O(nm)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                a,b = mydict[i],mydict[j]\n",
    "                r,c = len(a)+len(b),len(a.union(b))\n",
    "                ## O(n^2m)\n",
    "                if r!=c:\n",
    "                    similarity = 1.0*r/c-1+1e-9\n",
    "                    ans.append(\"%d,%d: %.4f\"%(i,j,similarity))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        docs = [set(i) for i in docs]\n",
    "        return [\"{:d},{:d}: {:.4f}\".format(j, i, 1e-8+len(docs[j] & docs[i])/len(docs[i] | docs[j])) for i, j in combinations(reversed(range(len(docs))), 2) if docs[j] & docs[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        ListSet = []\n",
    "        for i in range(len(docs)):\n",
    "            ListSet.append(set(docs[i]))\n",
    "        intersection = {}\n",
    "        union = {}\n",
    "        result = []\n",
    "        for i in range(len(ListSet)):\n",
    "            if i == len(ListSet) - 1:\n",
    "                break\n",
    "            for j in range((i + 1),len(ListSet)):\n",
    "                intersection = ListSet[i] & ListSet[j]\n",
    "                union = ListSet[i] | ListSet[j]\n",
    "                similarity = format(len(intersection) / len(union)+ 1e-9,'.4f')\n",
    "                if float(similarity) > 0 :\n",
    "                    result.append('{i},{j}: {similarity}'.format(i = i, j = j, similarity =similarity))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        mydict = {}\n",
    "        for i in range(n):\n",
    "            mydict[i] = set(docs[i])\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                a,b = mydict[i],mydict[j]\n",
    "                r,c = len(a)+len(b),len(a.union(b))\n",
    "                if r!=c:\n",
    "                    similarity = 1.0*r/c-1+1e-9\n",
    "                    ans.append(\"%d,%d: %.4f\"%(i,j,similarity))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        docs = [set(i) for i in docs]\n",
    "        ans = []\n",
    "        for i, j in combinations(reversed(range(len(docs))), 2):\n",
    "            common = docs[j] & docs[i]\n",
    "            if common:\n",
    "                ans.append(\"{:d},{:d}: {:.4f}\".format(j, i, 1e-8+len(common)/len(docs[i] | docs[j])))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        sets = [set()] * n\n",
    "        for i in range(n):\n",
    "            sets[i] = set(docs[i])\n",
    "\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                # print(i, j)\n",
    "                interset = sets[i] & sets[j]\n",
    "                if len(interset) == 0:\n",
    "                    continue\n",
    "                unionset = sets[i] | sets[j]\n",
    "                r = (p := len(sets[i] & sets[j])) / (len(sets[i]) + len(sets[j]) - p)\n",
    "                ret.append(f'{i},{j}: {r + 1e-9:.4f}')\n",
    "        \n",
    "        return ret\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        def my_round(x, bits=4):\n",
    "            assert bits >= 0, '请输入非负数'\n",
    "            x *= 10 ** (bits + 1)\n",
    "            if x % 10 >= 5:\n",
    "                x = (x // 10 * 10 + 10) / (10 ** (bits + 1))\n",
    "            else:\n",
    "                x = (x // 10 * 10) / (10 ** (bits + 1))\n",
    "            return x\n",
    "        length = len(docs)\n",
    "        for i in range(length):\n",
    "            docs[i] = set(docs[i])\n",
    "        res = []\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length):\n",
    "                set_i, set_j = docs[i], docs[j]\n",
    "                x = len(set_i & set_j)\n",
    "                if x == 0:\n",
    "                    continue\n",
    "                y = len(set_i | set_j)\n",
    "                res.append('{},{}: {:.4f}'.format(i, j, my_round(x / y)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def computeSimilarities(self, docs):\n",
    "        \"\"\"\n",
    "        :type docs: List[List[int]]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        def my_round(x, bits=4):\n",
    "            assert bits >= 0, '请输入非负数'\n",
    "            x *= 10 ** (bits + 1)\n",
    "            if x % 10 >= 5:\n",
    "                x = (x // 10 * 10 + 10) / (10 ** (bits + 1))\n",
    "            else:\n",
    "                x = (x // 10 * 10) / (10 ** (bits + 1))\n",
    "            return x\n",
    "        length = len(docs)\n",
    "        for i in range(length):\n",
    "            docs[i] = set(docs[i])\n",
    "        res = []\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length):\n",
    "                set_i, set_j = docs[i], docs[j]\n",
    "                x = len(set_i & set_j)\n",
    "                if x == 0:\n",
    "                    continue\n",
    "                y = len(set_i | set_j)\n",
    "                res.append('{},{}: {:.4f}'.format(i, j, my_round(x / y)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def computeSimilarities(self, docs):\n",
    "        \"\"\"\n",
    "        :type docs: List[List[int]]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        for i in range(len(docs)):\n",
    "            docs[i] = set(docs[i])\n",
    "        result = []\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                union = docs[i].union(docs[j])\n",
    "                intersection = len(docs[i]) + len(docs[j]) - len(union)\n",
    "                similarity = round(intersection / len(union) + 1e-9, 4)\n",
    "                if similarity > 0:\n",
    "                    result.append(f\"{i},{j}: {similarity:.4f}\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def computeSimilarities(self, docs):\n",
    "        \"\"\"\n",
    "        :type docs: List[List[int]]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        for i in range(len(docs)):\n",
    "            docs[i] = set(docs[i])\n",
    "        result = []\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                union = docs[i].union(docs[j])\n",
    "                intersection = len(docs[i]) + len(docs[j]) - len(union)\n",
    "                similarity = round(intersection / len(union) + 1e-9, 4)\n",
    "                if similarity > 0:\n",
    "                    result.append(f\"{i},{j}: {similarity:.4f}\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        m=len(docs)\n",
    "        red={}\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(i+1,m):\n",
    "                a=set(docs[i])\n",
    "                b=set(docs[j])\n",
    "                c=a-b\n",
    "                d=a-c\n",
    "                # print(i,j,a,b,c,d,len(d),red)\n",
    "                if len(d)>0:\n",
    "                    e=round(len(d)/((len(a)+len(b)-len(d))*1.0)+1e-9,4)\n",
    "                    red[str(i)+','+str(j)+': ']='%.4f'%e\n",
    "        rel=[]\n",
    "        for i in red:\n",
    "            rel.append(i+red[i])\n",
    "        return rel\n",
    "\n",
    "\n",
    "\n",
    "                # for k in docs[i]:\n",
    "                #     if k in b\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        reverseRank = defaultdict(list)\n",
    "        n = len(docs)\n",
    "        for did, doc in enumerate(docs):\n",
    "            for w in doc:\n",
    "                reverseRank[w].append(did)\n",
    "        \n",
    "        inters = [[0]*n for _ in range(n)]\n",
    "        for w in reverseRank:\n",
    "            doc_ids = reverseRank[w]\n",
    "            for i in range(len(doc_ids)):\n",
    "                id1 = doc_ids[i]\n",
    "                for j in range(i+1, len(doc_ids)):\n",
    "                    id2 = doc_ids[j]\n",
    "                    inters[id1][id2] += 1\n",
    "        \n",
    "        ret = []\n",
    "        for id1 in range(n):\n",
    "            for id2 in range(id1+1,n):\n",
    "                if inters[id1][id2] > 0:\n",
    "                    inter = inters[id1][id2]\n",
    "                    union = len(docs[id1]) + len(docs[id2]) - inter\n",
    "                    sim = 1.*inter / union\n",
    "                    ret.append(\"{0},{1}: {2:.4f}\".format(id1, id2, sim+1e-9))\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        record = collections.defaultdict(list)\n",
    "        arrray = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i, nums in enumerate(docs):\n",
    "            for num in nums:\n",
    "                record[num].append(i)\n",
    "        res =[]\n",
    "        for key, value in record.items():\n",
    "            m = len(value)\n",
    "            value.sort()\n",
    "            for i in range(m):\n",
    "                for j in range(i+1, m):\n",
    "                    arrray[value[i]][value[j]] += 1\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if arrray[i][j] > 0:\n",
    "                    rate = arrray[i][j]/(len(docs[i])+len(docs[j])-arrray[i][j])\n",
    "                    temp = '{:d},{:d}: {:.4f}'.format(i, j, rate+1e-9)\n",
    "                    # print(temp)\n",
    "                    res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        word_docs = {}\n",
    "        sims = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for word in docs[i]:\n",
    "                if word not in word_docs:\n",
    "                    word_docs[word] = [i]\n",
    "                else:\n",
    "                    for j in word_docs[word]:\n",
    "                        sims[i][j] += 1\n",
    "                        sims[j][i] += 1\n",
    "                    word_docs[word].append(i)\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if sims[i][j] > 0:\n",
    "                    result.append(\n",
    "                        f\"{i},{j}: {(sims[i][j]/(len(docs[i])+len(docs[j])-sims[i][j]) + 1e-9):.4f}\"\n",
    "                    )\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        cnt = collections.defaultdict(list)\n",
    "        sim = Counter()\n",
    "\n",
    "        for i, doc in enumerate(docs):\n",
    "            for d in doc:\n",
    "                for j in cnt[d]:\n",
    "                    sim[i, j] += 1 \n",
    "                cnt[d].append(i)\n",
    "        ls = [len(x) for x in docs]\n",
    "        res = []\n",
    "        for (i, j) in sim:\n",
    "            s = sim[i, j] / (ls[i] + ls[j] - sim[i, j]) + 1e-9\n",
    "            res.append(f\"{j},{i}: {s:.4f}\")\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = {}\n",
    "        n = len(docs)\n",
    "        # 建立字典1\n",
    "        for i in range(n):\n",
    "            v = docs[i]\n",
    "            for num in v:\n",
    "                dic1.setdefault(num, [])\n",
    "                dic1[num].append(i)\n",
    "        print(dic1)\n",
    "        dic2 = {}\n",
    "        for key, values in dic1.items():\n",
    "            len1 = len(values)\n",
    "            if len1 == 1:\n",
    "                continue\n",
    "            for i in range(len1-1):\n",
    "                num1 = values[i]\n",
    "                for j in range(i+1, len1):\n",
    "                    num2 = values[j]\n",
    "                    if (num1, num2) in dic2:\n",
    "                        dic2[(num1, num2)] += 1\n",
    "                        continue\n",
    "                    dic2[(num1, num2)] = 1\n",
    "        print(dic2)\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for key, value in dic2.items():\n",
    "            a, b = key\n",
    "            len2 = len(docs[a]) + len(docs[b]) - value\n",
    "            res = value / len2 + minn\n",
    "            ans.append('{},{}: {:.4f}'.format(key[0], key[1], res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        len_map = [len(x) for x in docs]  # 每个doc的长度\n",
    "        cnt = collections.defaultdict(list)  # 统计每个词在哪些字典里出现过\n",
    "        sim_cnt = collections.defaultdict(int)  # key为(id1, id2)，val为交集元素数量\n",
    "        for i, doc in enumerate(docs):\n",
    "            for word in doc:\n",
    "                if word in cnt.keys():\n",
    "                    for prev in cnt[word]: # 计数。此时cnt里文档的编号都小于i，所以可以在遍历文档的时候顺便计数\n",
    "                        sim_cnt[(prev, i)] += 1\n",
    "                cnt[word].append(i)\n",
    "        \n",
    "        ans = [\"\" for _ in range(len(sim_cnt))]\n",
    "        for i, (key, val) in enumerate(sim_cnt.items()):\n",
    "            id1, id2 = key\n",
    "            sim_score = val/(len_map[id1]+len_map[id2]-val)+1e-9  # 看评论区大佬说是浮点数精度问题\n",
    "            ans[i] = f\"{id1},{id2}: {sim_score:.4f}\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lenintersection(set1, lst):\n",
    "    num = 0\n",
    "    for v in lst:\n",
    "        if v in set1:\n",
    "            num += 1\n",
    "    return num\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = {}\n",
    "        n = len(docs)\n",
    "        # 建立字典1\n",
    "        for i in range(n):\n",
    "            v = docs[i]\n",
    "            for num in v:\n",
    "                dic1.setdefault(num, [])\n",
    "                dic1[num].append(i)\n",
    "\n",
    "        dic2 = {}\n",
    "        for key, values in dic1.items():\n",
    "            len1 = len(values)\n",
    "            if len1 == 1:\n",
    "                continue\n",
    "            for i in range(len1-1):\n",
    "                num1 = values[i]\n",
    "                for j in range(i+1, len1):\n",
    "                    num2 = values[j]\n",
    "                    if (num1, num2) in dic2:\n",
    "                        dic2[(num1, num2)] += 1\n",
    "                        continue\n",
    "                    dic2[(num1, num2)] = 1\n",
    "\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for key, value in dic2.items():\n",
    "            a, b = key\n",
    "            len2 = len(docs[a]) + len(docs[b]) - value\n",
    "            res = value / len2 + minn\n",
    "            ans.append('{},{}: {:.4f}'.format(key[0], key[1], res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import defaultdict\n",
    "# from typing import List\n",
    "# from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dict_word = defaultdict(list)               # 用于记录各个单词出现在哪些文档中\n",
    "        for common, doc in enumerate(docs):\n",
    "            for word in doc:\n",
    "                dict_word[word].append(common)\n",
    "\n",
    "        dict_compare = defaultdict(int)             # 用于记录两两文档之间的公共单词\n",
    "        for doc_ids in dict_word.values():\n",
    "            for i1, i2 in combinations(doc_ids, 2):\n",
    "                dict_compare[i1, i2] += 1\n",
    "\n",
    "        res = []\n",
    "        for (i1, i2), common in dict_compare.items():\n",
    "            union = len(docs[i1]) + len(docs[i2]) - common      # A ∪ B = A + B - A ∩ B\n",
    "            similarity = common / union + 1e-9\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(i1, i2, similarity))\n",
    "        return res\n",
    "\n",
    "\n",
    "# doc = [\n",
    "# [14, 15, 100, 9, 3],\n",
    "# [32, 1, 9, 3, 5],\n",
    "# [15, 29, 2, 6, 8, 7],\n",
    "# [7, 10]\n",
    "# ]\n",
    "# s = Solution()\n",
    "# print(s.computeSimilarities(doc))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        char_dict = defaultdict(list)\n",
    "        for doc_idx, doc in enumerate(docs):\n",
    "            for char in doc:\n",
    "                char_dict[char].append(doc_idx)\n",
    "\n",
    "        union_dict = Counter()\n",
    "        for doc_idxs in char_dict.values():\n",
    "            for i in range(len(doc_idxs)):\n",
    "                for j in range(i + 1, len(doc_idxs)):\n",
    "                    min_idx, max_idx = \\\n",
    "                        min(doc_idxs[i], doc_idxs[j]), max(doc_idxs[i], doc_idxs[j])\n",
    "                    union_dict[(min_idx, max_idx)] += 1\n",
    "\n",
    "        res = []\n",
    "        for (i, j), union_val in union_dict.items():\n",
    "            res.append(f\"{i},{j}: {union_val / (len(docs[i]) + len(docs[j]) - union_val)+1e-9:.4f}\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = {}\n",
    "        n = len(docs)\n",
    "        # 建立字典1\n",
    "        # dic1 = collections.defaultdict(list) 返回一个空字典，当访问元素时如果没有就会自动生成一个value，类型为[]\n",
    "        for i in range(n):\n",
    "            v = docs[i]\n",
    "            for num in v:\n",
    "                dic1.setdefault(num, [])\n",
    "                dic1[num].append(i)\n",
    "\n",
    "        dic2 = {}\n",
    "        for key, values in dic1.items():\n",
    "            len1 = len(values)\n",
    "            if len1 == 1:\n",
    "                continue\n",
    "            for i in range(len1-1):\n",
    "                num1 = values[i]\n",
    "                for j in range(i+1, len1):\n",
    "                    num2 = values[j]\n",
    "                    if (num1, num2) in dic2:\n",
    "                        dic2[(num1, num2)] += 1\n",
    "                        continue\n",
    "                    dic2[(num1, num2)] = 1\n",
    "\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for key, value in dic2.items():\n",
    "            a, b = key\n",
    "            len2 = len(docs[a]) + len(docs[b]) - value\n",
    "            res = value / len2 + minn\n",
    "            ans.append('{},{}: {:.4f}'.format(key[0], key[1], res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        dict1 = {}\n",
    "       ## why fast?\n",
    "       ## 同样的量级，但是注意稀疏性\n",
    "        for i in range(n):\n",
    "            for word in docs[i]:\n",
    "                if word not in dict1:\n",
    "                    dict1[word] = []\n",
    "                dict1[word].append(i)\n",
    "        ## O(mn)\n",
    "        dict2 = {}\n",
    "        ## len(v) is O(1) when sparse \n",
    "        for v in dict1.values():\n",
    "            if len(v) == 1:\n",
    "                continue\n",
    "            for x in range(len(v)-1):\n",
    "                ind1 = v[x]\n",
    "                for y in range(x+1,len(v)): \n",
    "                    ind2 = v[y]\n",
    "                    if (ind1,ind2) not in dict2:\n",
    "                        dict2[(ind1,ind2)] = 1\n",
    "                    else:\n",
    "                        dict2[(ind1,ind2)]+=1\n",
    "        ## O(mn^3)\n",
    "        for key,uni in dict2.items():\n",
    "\n",
    "            similarity = 1.0*uni/(len(docs[key[0]])+len(docs[key[1]])-uni)+1e-9\n",
    "            ans.append(\"%d,%d: %.4f\"%(key[0],key[1],similarity))\n",
    "        ## O(n^2)\n",
    "\n",
    "\n",
    "        ## O(mn) total when sparse\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs):\n",
    "        res=[]\n",
    "        n=len(docs)\n",
    "        dic1={}\n",
    "        for i in range(n):\n",
    "            for num in docs[i]:\n",
    "                if num not in dic1:\n",
    "                    dic1[num]=[]\n",
    "                dic1[num].append(i)\n",
    "        dic2={}\n",
    "        for v in dic1.values():\n",
    "            n = len(v)\n",
    "            if n==1:\n",
    "                continue\n",
    "            for i,j in combinations(v,2):\n",
    "                if (i,j) not in dic2:\n",
    "                    dic2[(i,j)] = 0\n",
    "                dic2[(i,j)] += 1\n",
    "        for k,v in dic2.items():\n",
    "            i,j=k\n",
    "            l1=len(docs[i])\n",
    "            l2=len(docs[j])\n",
    "            lt=l1+l2-v\n",
    "            res.append(\"{},{}: {:.4f}\".format(i, j, v / lt+1e-9))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1=collections.defaultdict(list)\n",
    "        for i,doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2=collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p+1,len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res=[]\n",
    "        minn=1e-9\n",
    "        for (p,q),i in dic2.items():\n",
    "            u=len(docs[p])+len(docs[q])-i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        char_dict = defaultdict(list)\n",
    "        for doc_idx, doc in enumerate(docs):\n",
    "            for char in doc:\n",
    "                char_dict[char].append(doc_idx)\n",
    "\n",
    "        union_dict = Counter()\n",
    "        for doc_idxs in char_dict.values():\n",
    "            for i in range(len(doc_idxs)):\n",
    "                for j in range(i + 1, len(doc_idxs)):\n",
    "                    min_idx, max_idx = \\\n",
    "                        min(doc_idxs[i], doc_idxs[j]), max(doc_idxs[i], doc_idxs[j])\n",
    "                    union_dict[(min_idx, max_idx)] += 1\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i + 1, len(docs)):\n",
    "                union_val = union_dict[(i, j)]\n",
    "                if union_val == 0: continue\n",
    "                res.append(f\"{i},{j}: {union_val / (len(docs[i]) + len(docs[j]) - union_val)+1e-9:.4f}\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "\n",
    "        def createNumToDocMap(documents):\n",
    "            numToDocMap = defaultdict(list)\n",
    "            for i, doc in enumerate(documents):\n",
    "                for num in doc:\n",
    "                    numToDocMap[num].append(i)\n",
    "            return numToDocMap\n",
    "\n",
    "        def createIntersectNumToDocMap(numToDocMap):\n",
    "            intersectNumToDocMap = defaultdict(int)\n",
    "            for l in numToDocMap.values():\n",
    "                for docA in range(len(l)):\n",
    "                    for docB in range(docA + 1, len(l)):\n",
    "                        intersectNumToDocMap[l[docA], l[docB]] += 1\n",
    "            return intersectNumToDocMap\n",
    "\n",
    "        numberToDocumentMap = createNumToDocMap(docs)\n",
    "        intersectNumToDocMap = createIntersectNumToDocMap(numberToDocumentMap)\n",
    "        res = []\n",
    "        for (p, q), intersect in intersectNumToDocMap.items():\n",
    "            union = len(docs[p]) + len(docs[q]) - intersect\n",
    "            res.append(str(p) + \",\" + str(q) + \": \" + str(format(intersect / union + 1e-9, '.4f')))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def main(docs):\n",
    "    res = []\n",
    "    dic1 = {}\n",
    "    for i in range(len(docs)):\n",
    "        for num in docs[i]:\n",
    "            if num not in dic1:\n",
    "                dic1[num] = []\n",
    "            dic1[num].append(i)\n",
    "    dic2 = {}\n",
    "    for v in dic1.values():\n",
    "        lv = len(v)\n",
    "        if lv == 1:\n",
    "            continue\n",
    "        for i in range(lv - 1):\n",
    "            x = v[i]\n",
    "            for j in range(i + 1, lv):\n",
    "                y = v[j]\n",
    "                if (x, y) not in dic2:\n",
    "                    dic2[(x, y)] = 0\n",
    "                dic2[(x, y)] += 1\n",
    "    print(dic2)\n",
    "    for k, v in dic2.items():\n",
    "        i, j = k\n",
    "        res.append('{},{}: {:.4f}'.format(i, j, v / (len(docs[i]) + len(docs[j]) - v)+1e-9))\n",
    "    return res\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        return main(docs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1=collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2=collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p+1,len(li)):\n",
    "                    dic2[li[p],li[q]]+=1\n",
    "        res=[]\n",
    "        minn=1e-9\n",
    "        for (p,q),i in dic2.items():\n",
    "            u=len(docs[p])+len(docs[q])-i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p,q,i/u+minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        len_map = [len(x) for x in docs]  # 每个doc的长度\n",
    "        word_d = collections.defaultdict(list)  # 倒排索引：统计每个词在哪些文档里出现过\n",
    "        intersect = collections.defaultdict(int)  # key为(id1, id2)，val为交集元素数量\n",
    "        for i, doc in enumerate(docs):\n",
    "            for word in doc:\n",
    "                if word in word_d.keys():\n",
    "                    # 计数：此时word_d里文档的编号都小于i，所以可以在遍历文档的时候顺便计数\n",
    "                    for prev in word_d[word]: \n",
    "                        intersect[(prev, i)] += 1\n",
    "                word_d[word].append(i)\n",
    "        \n",
    "        ans = [\"\" for _ in range(len(intersect))]\n",
    "        for i, (key, val) in enumerate(intersect.items()):\n",
    "            id1, id2 = key\n",
    "            sim_score = val/(len_map[id1]+len_map[id2]-val)+1e-9  # 看评论区大佬说是浮点数精度问题\n",
    "            ans[i] = f\"{id1},{id2}: {sim_score:.4f}\"\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        \n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        n = len(docs)\n",
    "        ans = []\n",
    "        dict1 = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            for word in docs[i]:\n",
    "                if word not in dict1:\n",
    "                    dict1[word] = []\n",
    "                dict1[word].append(i)\n",
    "        dict2 = {}\n",
    "        for v in dict1.values():\n",
    "            if len(v) == 1:\n",
    "                continue\n",
    "            for x in range(len(v)-1):\n",
    "                ind1 = v[x]\n",
    "                for y in range(x+1,len(v)): \n",
    "                    ind2 = v[y]\n",
    "                    if (ind1,ind2) not in dict2:\n",
    "                        dict2[(ind1,ind2)] = 1\n",
    "                    else:\n",
    "                        dict2[(ind1,ind2)]+=1\n",
    "        for key,uni in dict2.items():\n",
    "\n",
    "            similarity = 1.0*uni/(len(docs[key[0]])+len(docs[key[1]])-uni)+1e-9\n",
    "            ans.append(\"%d,%d: %.4f\"%(key[0],key[1],similarity))\n",
    "        return ans\n",
    "\n",
    "\n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def main(docs):\n",
    "    dic1 = {}\n",
    "    n = len(docs)\n",
    "    for i in range(len(docs)):\n",
    "        for num in docs[i]:\n",
    "            if num not in dic1:\n",
    "                dic1[num] = []\n",
    "            dic1[num].append(i)\n",
    "    print(dic1)\n",
    "    dic2 = {}\n",
    "    for a in dic1.values():\n",
    "\n",
    "        n = len(a)\n",
    "        if n == 1:\n",
    "            continue\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            x = a[i]\n",
    "            for j in range(i + 1, n):\n",
    "                y = a[j]\n",
    "                if (x, y) not in dic2:\n",
    "                    dic2[(x, y)] = 0\n",
    "                dic2[(x, y)] += 1\n",
    "\n",
    "        res = []\n",
    "    for a, b in dic2.items():\n",
    "        i, j = a\n",
    "        res.append('{},{}: {:.4f}'.format(i, j, (b / (len(docs[i]) + len(docs[j]) - b))+1e-9))\n",
    "    return res\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        return main(docs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def func1(lst1,lst2):\n",
    "#     sum_int = 0\n",
    "#     for i in lst1:\n",
    "#         if i in lst2:\n",
    "#             sum_int += 1\n",
    "#     return sum_int\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        # n = len(docs)\n",
    "        # ans = []\n",
    "        # for i in range(n-1):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         n1 = len(docs[i])\n",
    "        #         n2 = len(docs[j])\n",
    "        #         n3 = len(set(docs[i]).intersection(docs[j]))\n",
    "        #         # n3 = func1(docs[i],docs[j])\n",
    "        #         if n3 == 0:\n",
    "        #             continue\n",
    "        #         n4 = n1+n2-n3\n",
    "        #         ans.append(\"{},{}: {:.4f}\".format(i,j,n3/n4+1e-9))\n",
    "        # return ans\n",
    "        res = {}\n",
    "        n = len(docs)\n",
    "        for i in range(n):\n",
    "            for j in docs[i]:\n",
    "                if j not in res:\n",
    "                    res[j] = []\n",
    "                res[j].append(i)\n",
    "        res1 = {}\n",
    "        for id1,id2 in res.items():\n",
    "            if len(id2) == 1:\n",
    "                continue\n",
    "            # for l in range(len(id2)-1):\n",
    "            #     for m in range(l+1,len(id2)):\n",
    "            for i,j in combinations(id2,2):\n",
    "                    # i = id2[l]\n",
    "                    # j = id2[m]\n",
    "                if (i,j) not in res1:\n",
    "                    res1[(i,j)] = 0\n",
    "                res1[(i,j)] += 1\n",
    "        ans = []\n",
    "        for id1,id2 in res1.items():\n",
    "            i,j = id1\n",
    "            n1 = len(docs[i])\n",
    "            n2 = len(docs[j])\n",
    "            n3 = n1+n2-id2\n",
    "            ans.append(\"{},{}: {:.4f}\".format(i,j,id2/n3+1e-9))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        rec = {}\n",
    "        ans = {}\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                if num not in rec:\n",
    "                    rec[num] = []\n",
    "                for index in rec[num]:\n",
    "                    ans[(index, i)] = ans.get((index, i), 0) + 1\n",
    "                rec[num].append(i)\n",
    "                #\n",
    "        ret = [f\"{ind1},{ind2}: {val/(len(docs[ind1])+len(docs[ind2])-val)+1e-9:.4f}\"\n",
    "            for (ind1, ind2), val in ans.items()]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        len_map = [len(x) for x in docs]  # 每个doc的长度\n",
    "        cnt = collections.defaultdict(list)  # 统计每个词在哪些字典里出现过\n",
    "        sim_cnt = collections.defaultdict(int)  # key为(id1, id2)，val为交集元素数量\n",
    "        for i, doc in enumerate(docs):\n",
    "            for word in doc:\n",
    "                if word in cnt.keys():\n",
    "                    for prev in cnt[word]: # 计数。此时cnt里文档的编号都小于i，所以可以在遍历文档的时候顺便计数\n",
    "                        sim_cnt[(prev, i)] += 1\n",
    "                cnt[word].append(i)\n",
    "        \n",
    "        ans = [\"\" for _ in range(len(sim_cnt))]\n",
    "        for i, (key, val) in enumerate(sim_cnt.items()):\n",
    "            id1, id2 = key\n",
    "            sim_score = val/(len_map[id1]+len_map[id2]-val)+1e-9  # 看评论区大佬说是浮点数精度问题\n",
    "            ans[i] = f\"{id1},{id2}: {sim_score:.4f}\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        eps = 1e-9\n",
    "\n",
    "        dn = len(docs)\n",
    "\n",
    "        num_ids = defaultdict(list)\n",
    "\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                num_ids[num].append(i)\n",
    "        \n",
    "        ab_intersect_cnt = defaultdict(int)\n",
    "        for num, ids in num_ids.items():\n",
    "            n = len(ids)\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    ab_intersect_cnt[ids[i], ids[j]] += 1\n",
    "        \n",
    "        res = []\n",
    "        for (a, b), intersect_cnt in ab_intersect_cnt.items():\n",
    "            union_cnt = len(docs[a]) + len(docs[b]) - intersect_cnt\n",
    "            rate = intersect_cnt / union_cnt + eps\n",
    "            tmp = \"{},{}: {:.4f}\".format(a, b, rate)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res\n",
    "#出自cxsy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1=collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2=collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p+1,len(li)):\n",
    "                    dic2[li[p],li[q]]+=1\n",
    "        res=[]\n",
    "        minn=1e-9\n",
    "        for (p,q),i in dic2.items():\n",
    "            u=len(docs[p])+len(docs[q])-i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p,q,i/u+minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        eps = 1e-9\n",
    "\n",
    "        dn = len(docs)\n",
    "\n",
    "        num_ids = defaultdict(list)\n",
    "\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                num_ids[num].append(i)\n",
    "        \n",
    "        ab_intersect_cnt = defaultdict(int)\n",
    "        for num, ids in num_ids.items():\n",
    "            n = len(ids)\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    ab_intersect_cnt[ids[i], ids[j]] += 1\n",
    "        \n",
    "        res = []\n",
    "        for (a, b), intersect_cnt in ab_intersect_cnt.items():\n",
    "            union_cnt = len(docs[a]) + len(docs[b]) - intersect_cnt\n",
    "            rate = intersect_cnt / union_cnt + eps\n",
    "            tmp = \"{},{}: {:.4f}\".format(a, b, rate)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = collections.defaultdict(list)\n",
    "        for i, doc in enumerate(docs):\n",
    "            for num in doc:\n",
    "                dic1[num].append(i)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for li in dic1.values():\n",
    "            for p in range(len(li)):\n",
    "                for q in range(p + 1, len(li)):\n",
    "                    dic2[li[p], li[q]] += 1\n",
    "        res = []\n",
    "        minn = 1e-9\n",
    "        for (p, q), i in dic2.items():\n",
    "            u = len(docs[p]) + len(docs[q]) - i\n",
    "            res.append(\"{0:d},{1:d}: {2:.4f}\".format(p, q, i / u + minn))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic = defaultdict(list)\n",
    "    \n",
    "        num = {}\n",
    "        for i, doc_i in enumerate(docs):\n",
    "            for j, num_j in enumerate(doc_i):\n",
    "         \n",
    "                dic[num_j].append(i)\n",
    "\n",
    "        for l in dic.values():\n",
    "            l = list(l)\n",
    "            \n",
    "            for i in range(len(l)):\n",
    "                for j in range(i+1, len(l)):\n",
    "                    num[(l[i], l[j])] = num.get((l[i], l[j]), 0) + 1\n",
    "\n",
    "        ans = []\n",
    "      \n",
    "        for k, v in num.items():\n",
    "       \n",
    "            ans.append('{},{}: {:.4f}'.format(k[0],k[1], 1e-9 + v/(len(docs[k[0]]) + len(docs[k[1]])-v)))\n",
    "\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef computeSimilarities(self, docs):\n",
    "\t\tlens = [len(doc) for doc in docs]\n",
    "\t\tmap0 = {}\n",
    "\t\tfor i, doc in enumerate(docs):\n",
    "\t\t\tfor num in doc:\n",
    "\t\t\t\tif num in map0:\n",
    "\t\t\t\t\tmap0[num].append(i)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tmap0[num] = [i]\n",
    "\t\tmap1 = {}\n",
    "\t\tfor num in map0:\n",
    "\t\t\tn = len(map0[num])\n",
    "\t\t\tif n >= 2:\n",
    "\t\t\t\tids = map0[num]\n",
    "\t\t\t\tfor i in range(n):\n",
    "\t\t\t\t\tfor j in range(i):\n",
    "\t\t\t\t\t\tmap1[(ids[j], ids[i])] = map1.get((ids[j], ids[i]), 0) + 1\n",
    "\t\tans = []\n",
    "\t\tfor key in map1:\n",
    "\t\t\tmod = lens[key[0]] + lens[key[1]] - map1[key]\n",
    "\t\t\tif map1[key] == mod:\n",
    "\t\t\t\tvs = '1.0000'\n",
    "\t\t\telse:\n",
    "\t\t\t\td = map1[key] * 10000 // mod\n",
    "\t\t\t\tr = map1[key] * 10000 % mod\n",
    "\t\t\t\tif r * 2 >= mod:\n",
    "\t\t\t\t\td += 1\n",
    "\t\t\t\tvs = '0.' + '0' * (4 - len(str(d))) + str(d)\n",
    "\t\t\tans.append(str(key[0]) + ',' + str(key[1]) + ': ' + vs)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "\n",
    "        res = []\n",
    "        d1 = {}\n",
    "        for i,v1 in enumerate(docs):\n",
    "            for v2 in v1:\n",
    "                if v2 not in d1:\n",
    "                    d1[v2] = [i]\n",
    "                else:\n",
    "                    d1[v2].append(i)\n",
    "        d2 = {}\n",
    "        for k,v in d1.items():\n",
    "            n = len(v)\n",
    "            if n == 1:\n",
    "                continue\n",
    "            for i in range(n - 1):\n",
    "                for j in range(i + 1,n):\n",
    "                    if (v[i],v[j]) not in d2:\n",
    "                        d2[(v[i],v[j])] = 1\n",
    "                    else:\n",
    "                        d2[(v[i],v[j])] += 1\n",
    "\n",
    "        for k,v in d2.items():\n",
    "            i,j = k\n",
    "            n = len(docs[i]) + len(docs[j])\n",
    "            minn = 1e-9\n",
    "            length = v/(n-v) + minn\n",
    "            res.append(\"{},{}: {:.4f}\".format(i, j, length))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic1 = {}\n",
    "        n = len(docs)\n",
    "        # 建立字典1\n",
    "        for i in range(n):\n",
    "            v = docs[i]\n",
    "            for num in v:\n",
    "                if num in dic1:\n",
    "                    dic1[num].append(i)\n",
    "                    continue\n",
    "                dic1[num] = [i]\n",
    "\n",
    "        dic2 = {}\n",
    "        for key, values in dic1.items():\n",
    "            len1 = len(values)\n",
    "            if len1 == 1:\n",
    "                continue\n",
    "            for i in range(len1-1):\n",
    "                num1 = values[i]\n",
    "                for j in range(i+1, len1):\n",
    "                    num2 = values[j]\n",
    "                    if (num1, num2) in dic2:\n",
    "                        dic2[(num1, num2)] += 1\n",
    "                        continue\n",
    "                    dic2[(num1, num2)] = 1\n",
    "\n",
    "        ans = []\n",
    "        minn = 1e-9\n",
    "        for key, value in dic2.items():\n",
    "            a, b = key\n",
    "            len2 = len(docs[a]) + len(docs[b]) - value\n",
    "            res = value / len2 + minn\n",
    "            ans.append('{},{}: {:.4f}'.format(key[0], key[1], res))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from decimal import *\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        dic = dict()\n",
    "        eps = 1e-9\n",
    "\n",
    "        for i in range(len(docs)):\n",
    "            subList = docs[i]\n",
    "            for e in subList:\n",
    "                if e in dic:\n",
    "                    dic[e].add(i)\n",
    "                else:\n",
    "                    dic[e] = set()\n",
    "                    dic[e].add(i)\n",
    "        \n",
    "        res = []\n",
    "        dic2 = dict()\n",
    "        for i in range(len(docs)):\n",
    "            subList = docs[i]\n",
    "            dic2.clear()\n",
    "            for e in subList:\n",
    "                for index in dic[e]:\n",
    "                    if index > i:\n",
    "                        if index not in dic2:\n",
    "                            dic2[index] = 1\n",
    "                        else:\n",
    "                            dic2[index] += 1\n",
    "            \n",
    "            for key in dic2.keys():\n",
    "                rate = dic2[key] / (len(docs[i]) + len(docs[key]) - dic2[key]) + eps\n",
    "                res.append(str.format('{},{}: {:.4f}', i, key, rate))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:\n",
    "        ans=[]\n",
    "        from collections import defaultdict\n",
    "        daopai=defaultdict(set)\n",
    "        for ind,i in enumerate(docs):\n",
    "            for j in i:\n",
    "                daopai[j].add(ind)\n",
    "        def calc(i,j):\n",
    "            same=0\n",
    "            if len(docs[i])>len(docs[j]):\n",
    "                i,j=j,i\n",
    "            for x in docs[i]:\n",
    "                if j in daopai[x]:\n",
    "                    same+=1\n",
    "            return same,(len(docs[i])+len(docs[j])-same)\n",
    "        for i in range(len(docs)):\n",
    "            for j in range(i+1,len(docs)):\n",
    "                up,down=calc(i,j)\n",
    "                if down==0 or up==0:\n",
    "                    continue\n",
    "                if up>0:\n",
    "                    ans.append(f\"{i},{j}: {up/down+1e-10:.4f}\")\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
